
package tub.adm1;

import tub.adm1.GoldbergTarjan.Edge;

/**
 * @author a.lunkeit - alunkeit(at)gmail(dot)com
 *
 */
public class PushRelabel
{
  static final float epsilon = 0.01f;
  
  static void push( float[][] C, float[][] F, float[] excess, int u, int v ) 
  {
    float send = Math.min(excess[u], C[u][v] - F[u][v]);
    
    F[u][v] += send;
    F[v][u] -= send;
    excess[u] -= send;
    excess[v] += send;
  }
  
  static void push1( float[][] C, float[][] F, float[] excess, int u, int v ) 
  {
    float send = Math.min(excess[u], C[u][v] - F[u][v]);
    
    F[u][v] += send;
    F[v][u] -= send;
    excess[u] -= send;
    excess[v] += send;
    
    //if( send < epsilon )
    //  excess[ u ] = 0;
  }
   
  static void relabel(float[][] C, float[][] F, int[] height, int u) 
  {
    int v;
    int min_height = Integer.MAX_VALUE;
    
    for (v = 0; v < NODES; v++) 
    {
      if (C[u][v] - F[u][v] > 0) 
      {
        min_height = Math.min(min_height, height[v]);
        height[u] = min_height + 1;
      }
    }
  };
   
  static void discharge( float[][] C, float[][] F, float[] excess, int[] height, int[] seen, int u) 
  {
    while (excess[u] > epsilon ) 
    {
      System.out.println( "excess " + u + " := " + excess[ u ]);
      
      if (seen[u] < NODES) 
      {
        int v = seen[u];
        
        if ((C[u][v] - F[u][v] > epsilon ) && (height[u] > height[v])) 
        {
          push(C, F, excess, u, v);
        }
        else
        {
          seen[u] += 1;
        }
      } 
      else 
      {
        relabel(C, F, height, u);
        seen[u] = 0;
      }
    }
  }
   
  static void moveToFront(int i, int A[]) {
    int temp = A[i];
    int n;
    
    for (n = i; n > 0; n--)
    {
      A[n] = A[n-1];
    }
    A[0] = temp;
  }
   
  static float pushRelabel(float[][] C, float[][] F, int source, int sink) 
  {
    float[] excess;
    int [] height, seen; 
    int[] list;
    int i, p;
   
    excess = new float[NODES];
    height = new int[NODES];
    seen = new int[NODES];
   
    list = new int[ NODES - 2 ];
   
    for (i = 0, p = 0; i < NODES; i++)
    {
      if((i != source) && (i != sink)) 
      {
        list[p] = i;
        p++;
      }
    }
   
    height[source] = NODES;
    excess[source] = Integer.MAX_VALUE;
    
    for (i = 0; i < NODES; i++)
      push1(C, F, excess, source, i);
   
    p = 0;
    
    while (p < NODES - 2) 
    {
      int u = list[p];
      float old_height = height[u];
      
      discharge(C, F, excess, height, seen, u);
      
      if (height[u] > old_height) 
      {
        moveToFront(p,list);
        p=0;
      }
      else
        p += 1;
    }
    
    float maxflow = 0;
    
    for (i = 0; i < NODES; i++)
      maxflow += F[source][i];
   
    return maxflow;
  }
   
  static void printMatrix( float M[][]) {
    int i,j;
    for (i = 0; i < NODES; i++) 
    {
      for (j = 0; j < NODES; j++)
        System.out.print( M[i][j] + "\t" );
      System.out.println();
    }
  }
  
  protected static int NODES = 6;
  
  public static void grid50d()
  {
    try
    {
      float cap[][] = new float[NODES][NODES];
      float flow[][] = new float[NODES][NODES];
      
      Graph g = new Graph( );
      g.init( "cat/maxflows/Grid50x50D.cat"  );
      
      NODES = g.vertexCnt();
      
       cap = new float[ g.vertexCnt() ][ g.vertexCnt() ];
       flow = new float[ g.vertexCnt() ][ g.vertexCnt() ];
 
     for( Edge e : g.getEdges())
     {
       cap[ e._tailId -1 ][ e._headId -1] = e._weight;
       flow[ e._tailId -1 ][ e._headId -1] = 0;
     }
     
     
      System.out.println("Max Flow: " + pushRelabel(cap, flow, 2499, 0 ));
    }
    catch( Exception e )
    {
      e.printStackTrace();
    }
  }
   
  public static void main(String args[]) 
  {
    NODES = 5;
    
    grid50d();
  }



}
